963 63
868841013 340859100 324534093 211837420 384930351 134837885 586450299 268503124 511565005 348275998 453909737 253470661 893019445 737252101 94040167 813534014 605094014 675029387 570927605 45710354 610124342 182943645 661676877 524300394 921346781 634755646 48757334 921671103 689041000 274046211 902098354 115572068 114141374 890309781 221032753 139020026 272280126 162624819 10366044 384546553 909254200 728556333 868899563 301800750 779490159 535141226 616151375 511000887 745171614 904601571 773824809 350115081 118196463 304820262 666909649 601522027 930971781 793254356 476213456 434019960 58623220 660417827 719580262 564111393 789152707 345381724 921610245 831878313 631299825 383506782 529708243 679363367 71889773 7824409 841690156 841782279 762611101 338782996 484682782 850310025 378861016 943363816 811518956 448055361 699088108 281210307 655157900 816947093 580081305 585269734 378045225 746566210 290642963 505805351 66196897 716167384 868567684 808074352 328453895 415353913 265060231 251559486 200552482 290305054 312484270 537600291 935040493 99818386 505821438 699848004 555544597 899607925 236002670 939676635 410042238 148099834 367314796 569821110 639861951 518943273 601375831 143744438 455905953 636697182 65732869 756743505 54892707 527872712 849765439 567864081 450827641 96073963 331578689 341757715 304220041 778674974 127174203 968257417 848644972 452947726 244859602 835747640 928573555 244096057 320503455 286809595 505255200 413117044 218349999 655546174 968723368 520916582 374213889 137365635 729053816 799128586 249453323 735833569 58640557 302477105 330066486 683053184 920672922 755988990 143328605 30949150 494579782 213474664 815956562 910891661 873042923 81914299 780497497 333269554 157279353 962896663 45759659 439758472 200279568 722076656 923995381 648107419 22530697 601282444 972736470 822164366 323145710 622357128 870097764 452635925 895334142 643246420 937432488 861604859 14678442 652071090 369282845 91730846 391566747 679659579 186272053 323805038 234455209 987607258 893658836 451185522 605321573 530871630 599657171 908299970 709106064 844309677 329560702 391923214 284267682 182418652 519502871 60863509 36985412 574629655 96498001 800970799 791522006 751656047 622410709 202779332 103603690 690883655 379168704 943775699 837556935 637270743 628996131 749246316 8467175 60221353 212511106 509337654 825581177 144682527 180029526 178362858 471301855 326951915 151697803 864299477 693263665 106021780 907902722 953867610 432309945 874954488 825346064 896036974 432619893 853620165 194718718 256331803 120565401 326843390 289742983 672837373 766271242 462829180 76319324 40051144 654391267 979092330 697492899 240954304 63367924 198593736 259623028 659893567 597568318 198407914 99237723 259071538 708276600 186417910 422139353 544061597 979928205 919740777 802717411 846584083 202030108 448864403 984584033 25977150 804265719 672871190 729656496 191079517 269624228 809973867 378730785 675329473 594199775 112532317 344487032 841579855 885270038 582800011 921589869 448827393 909133292 835114730 39835950 736114789 296767158 636724802 154130395 48279324 698771713 123134892 28510985 860328796 101192714 62867482 924074304 898426735 403500100 63016655 806782333 52110642 105383382 101148131 992032177 484093079 582081306 43751104 543318335 896262179 565757216 747657896 690286978 438872944 852120104 46451500 463091269 229601196 349301292 881865910 493329993 671175193 453282644 584400128 166914498 982988427 392745087 354022299 799877850 615220717 699846081 998302826 546480685 177147068 560047839 656535076 599580492 314656138 123086293 669255381 407012666 323928444 867279696 336763485 370225394 559826125 208833845 221407471 325997535 341227849 582346008 870253460 823533665 31624915 171855046 392545446 710104143 808694751 437107387 597723733 897454960 203271160 241234604 899764005 663994881 267513915 66467839 447572590 399780658 533204442 293419086 919702235 765418409 144285339 552513512 992367852 193543677 498871127 485460560 856695668 321130300 320811131 518505660 655099931 467955045 212818570 573870231 133417948 509833199 972881048 559813119 557308296 400548929 727042257 656593480 978975298 953895479 2631920 910955127 249989634 461980836 623286984 823445959 44192786 103094730 992547519 722761768 38162836 342282723 453513806 48481979 290342905 741680540 632915586 463745623 587990411 601163925 477603454 99195911 165711844 891423714 297749495 317741962 944041077 54919309 157334966 647791058 660859136 577095697 782749722 646932357 916459551 800957152 664803219 562148735 516132795 704182495 845667624 926159694 983703957 336599525 282530034 69170613 39390144 695414335 922385055 593069865 384687396 128772911 478864368 599070295 507381245 278745960 781701947 997055132 777067611 266860436 129492457 704688267 114058400 179429070 135419641 411560043 847198213 381489448 858179452 937059511 521496340 400766503 347538711 951330460 447936559 58104642 850339972 483147902 142999048 869671526 827118097 732812403 142733863 729536629 404513823 486140614 865502568 99721154 978016164 504626806 948842106 178506390 818209962 602663860 764740193 599274415 194895053 64000617 5307636 32558780 373638593 2623661 456127327 96179426 720231370 159761233 554545827 116368698 497024579 570003030 664958481 914650448 842676760 965453172 49026003 950171558 933575243 525382292 699543907 281139759 495264370 95556694 125305874 380384980 138944311 961898124 945966979 996677618 452394199 747304637 487409197 807761626 599991204 334300835 527594972 18945616 548969603 285484205 448430128 787906829 162160495 773652094 952438044 594371133 419485172 363088748 400428904 617737730 271212980 789205250 305454384 297882095 920734950 549024638 1285220 642047373 898109138 349895764 771857734 854437593 165588566 67345065 245526254 419532996 393426532 368882648 642978761 872170930 618940033 971422705 782048278 983163900 216081224 616707125 504258152 48836718 624355557 696802203 757565991 223400649 78589339 263365967 483043854 788859970 485657151 216996653 369994926 234138625 560318138 436729418 737251050 514280867 80246922 203967852 301878905 738759609 263038785 297087373 226744424 120625223 484247301 74653788 237918101 354824006 838009103 745893563 796983605 480704290 141283372 304813890 420689230 100716860 69209407 586053307 861699902 566454377 904269757 874367140 764400690 524347249 383517231 466957744 296279984 176441233 282927795 549699654 810035726 174776057 418041724 794361088 486961912 996414287 105272142 98200366 513901038 774896171 511678979 425809745 260760259 467154329 427391752 667171232 807639583 154071194 538369504 95498374 121550846 947146658 453011104 453115681 606556720 570342171 95230577 289226693 612397271 450897377 48265746 61638775 451084011 749849541 113582164 253628787 978884281 261517835 138609820 934978983 920128608 218852843 760195940 825084725 799897171 592334611 150905529 523677685 944780250 82151459 249331390 768511472 414698896 815183151 276005417 322096614 787209702 714216001 8110785 864338889 216784287 948393429 257497574 34842944 664106578 353533788 878442761 620649509 296294124 426469305 662412847 390589191 79863851 881470919 80344178 529719721 237514531 258166992 964762752 523897729 655431101 436616983 737712410 466655802 456222003 993876560 907456918 160394802 948310166 301064227 312345694 963736317 589051208 924180140 304494447 538573280 821812610 447758590 240175835 637311575 850215631 689750427 47845191 356908687 707803279 281509629 632255598 779537900 167244406 711793681 925894044 9448325 615748362 339991735 772531251 901897891 580530728 994721347 233348137 88878406 540465535 318617599 89048200 273529504 519172371 191116199 844519406 391258519 592062908 506190827 368896779 286504263 119450532 521347312 188768549 995613566 253698765 943385296 149617814 946261823 437661577 237829653 483967309 49968448 328025856 704620098 991716681 231975531 492213677 673118282 899354914 567655520 504972769 100758295 34435712 77917170 459496511 598603268 181121185 770582950 123157566 914256227 736140503 690737719 19843755 45349113 373815560 580654868 896679972 145123453 563952685 19741408 344140701 249073692 454450387 780081138 521250015 289829112 292357021 959770835 422429444 667459492 626257855 602054850 328258813 626995882 638026117 417442355 101815308 273793285 359567050 177906507 429462090 128596135 128937345 426853478 225615650 945584884 800499248 717042834 464261588 816054085 129957488 967033361 432355315 14468455 808791918 34954459 419987431 307736089 524954733 636244761 690226028 215140242 42985794 476163499 867631122 156074488 410273495 952900260 727867323 901072361 452814248 490050504 822841631 831386358 134825545 174866197 977312843 687935011 527120350 494241079 30776093 525504105 219108513 517496338 161071562 500033333 136496223 706845500 404643161 709100774 145504507 152687231 822781478 496127826 537734890 853366364 865491552 65675329 372919734 318526595 587842698 400446961 691094140 366921821 893359614 130464145 679584365 137228162 178082149 479307718 82392912 48738883 382013760 704079656 71088126 57578017 370896995 372209862 296105189 446938707 794967668 488140446 480100486 838654021 203201648 249522214 580911608 649082899 866084135 920190150 670469474 91346706 615763387 574297691 472498308 834487368 294425125 663938998 322720559 142925551 857833392 496863003 402288584 253153014 773942652 877617859 486465994 870277504 385759484 777036122 346084417 796831586 256018040 615556225 559896143 806050217 724343180 251805005 205969322 672420370 608585639 431547078 310319900 688222097
622093453 376319081 221696258 852685515 250161366 999770791 685241294 752193691 228843117 806318948 454725253 533984401 1458961 924620408 63506754 50401646 243040983 845442097 201830321 513446313 566601894 537393104 591806869 725873645 317613241 414261767 117218114 799015832 129747745 431467905 164719139 956766526 524625985 620031834 957317429 781796133 223948624 990158755 119942026 384714182 759433946 900318688 640703688 609540690 647006528 423797129 461203879 399352107 699540275 906590348 516848247 808082022 394633789 897451977 274331543 986403920 981593912 489920917 300822527 551818214 667088084 201689144 495762871 985914203 636609558 575828591 969293406 186573462 581561043 446504938 264821668 434874289 285930553 333200847 625091536 574040443 736249159 366754101 625543226 414809591 220866384 802758058 368379346 264273627 55922301 571857326 1907608 911643666 35456583 365908278 377870625 933773883 200217600 337146410 202611993 262669607 66960203 890100454 286204859 612646494 90384544 389249213 792317275 350256027 29986762 73472113 826631901 745495884 994221672 357300413 777151546 970387731 518590063 223801035 879762690 818028103 589631654 226663102 126505685 323547764 887883048 737247274 410303977 44760022 385663974 826417303 366071175 138000354 698357539 492313089 239031950 555457982 431304182 391714139 328482799 651379396 165796043 88869639 49276207 653413635 412130274 271415647 198874856 25413054 229606863 551099184 245331272 625975275 887351288 406647354 211692688 215719092 550183194 577576369 653507990 784109050 357014981 113469631 331000387 572015309 127683291 533715199 576294422 76377589 738592277 451506948 742450336 704680044 248103038 188733136 392802310 657987554 754169078 847927389 97784706 425702200 366810288 261929496 453696482 903392517 992728500 43210080 954070024 445798932 821306718 442666764 227561832 845975012 965253341 949414370 940863117 216905511 749558709 710505249 469499796 201288259 246475837 452475128 209326767 628660692 518472738 8588556 378565795 482544936 92688098 379223798 61637962 581709505 939709010 309119171 866427410 840557271 980759833 318996850 362908797 843328980 884426546 182767481 149733023 188649174 264350830 328611649 405004707 540555312 741084912 337220005 83537990 918145001 334606255 306974839 316773210 436263995 714747639 708802300 644097605 347358741 807034600 219971691 392706943 194876314 595513334 780602993 442397976 678499488 853383527 79393199 341431599 318232370 242172376 650163259 16271484 254097423 75190201 140972571 658842823 804929320 600634828 408072653 585142126 369465893 549428138 569075906 640395747 409835233 170334270 692817374 805520428 197469674 246756935 359718394 738083170 31294722 648311514 182672994 251076146 375575968 762558943 62911832 305132895 548066160 464463503 485947535 434425406 632208079 702861820 717581744 720158008 425904976 707465097 777907928 5237835 394636345 53689198 169777432 936803210 680674054 425096501 435968756 496821656 346598885 941060160 301005029 894444081 782736953 136246849 135687127 801425058 954089240 716332991 472974251 935398476 832205261 818230936 633535414 753943333 876289110 709074553 502581057 714533942 579251686 845444968 512482311 881640478 548556133 443839035 301079226 989864333 717588971 129709854 465548157 981604298 519075656 853450769 506326123 792069934 595059840 195369320 527157775 680834471 416640071 307501129 512922090 321483062 272626057 304192305 935023345 39316593 630720997 750575728 505401356 942705922 937390124 713847464 418613400 346462757 377596135 715045714 981872358 21292334 366222543 655048505 817211578 682259457 115317075 828920060 286787020 490023832 619203861 152076688 157752394 373921409 582645869 743260860 687819605 918099805 429526501 27757980 659765119 371634019 132791995 11405599 391130451 279915226 769789794 593908873 891003853 343683490 888980993 751994866 855532254 144025004 873313522 758811844 965336042 977611645 842184004 650025024 409350729 591941296 105431354 276286458 803384777 591431281 558476490 284930649 678734122 615095298 576537631 635327256 230892705 805761337 4713496 535735752 707686486 703031040 604413126 921378380 321267429 261300692 366972402 415029595 846806497 6905415 381276564 577863425 426157645 66841471 779009629 434363678 90049313 938092468 982945326 709070821 841633739 608176821 540833951 637960799 171208363 172888164 816117113 524907238 328763797 16871221 560523068 940027818 952085075 75869364 73815962 527949103 810072865 680089084 271899130 930914509 295045423 83255872 651471862 565723951 597131043 676133701 163723741 218832085 471069588 133257190 630540594 41984658 909794192 68281999 41628971 65939982 848538903 602174403 670398258 463784516 457195421 617980055 618569064 131836421 317638284 350602548 630818589 717263988 296265663 209723224 806562137 793081225 249845257 680434902 749198167 970290830 139528108 73849361 103042820 43437732 214443234 779013765 185356164 718030655 200177240 47735615 509985198 30384294 884610990 215526752 941399179 242348148 387067896 835097757 762337243 776708634 804523584 563692482 985159823 348184922 698659329 667182378 629370192 218669773 829337006 633338697 827833591 615562847 598145321 57078051 693344531 446684622 198784588 590042322 328589414 291919150 838256996 699347971 738491240 964587367 848305072 681387641 651066051 92310197 553233382 847359113 924245461 720513320 192041135 261471133 373838641 995151650 695962918 298838193 131802910 537786331 56056158 934637785 252513814 889460192 174385881 926139833 331336521 377048976 778230545 187728395 865114904 700872094 778449394 304760349 919371162 300261266 781128286 171184720 352217882 791264328 872033960 695382426 175533718 448809071 539666201 221575685 358125634 820836618 132794479 683474222 81637379 281149427 746420313 567477447 929905653 741569619 40455676 815812885 875601126 349095212 399344241 825982834 72019672 364595663 906873668 70651084 821159299 854534758 586114295 847490084 459073232 540679787 503973757 556010769 635771231 807153455 409084607 764049978 378327810 442155604 279583002 294530015 239680320 554284627 409863647 180903505 881733587 79523576 512853970 495991414 596019498 506201057 439445420 874815046 35975400 906819842 887423130 465168208 950312035 876176163 55746747 436264246 291847461 175013984 921015205 997471276 812010863 996178600 150111968 86815101 36180657 498298432 99382889 737870854 607992339 379467837 823765297 967751865 439873264 302453005 51132828 833074460 145790293 90335471 753605123 821538247 785753223 569820278 429332786 478427882 281665914 519957258 516043498 571297476 673626970 768840038 363739744 842544685 618256390 67729435 517731516 266740493 155194512 710784524 416778652 103417570 501874622 700524784 793384846 494955327 169072268 33003988 981539481 478538311 841085096 289650582 693464245 748317494 838084853 865161579 178439246 190649561 220598281 540669273 74132165 104625168 734226094 248493246 829697263 58848339 360903780 593339591 818814356 306172458 351988702 672033018 395313649 199903668 594123137 824809389 716246582 921589537 853554664 619158156 656062985 32345400 238064738 889635095 614445314 924815826 327164786 434435873 614465837 35667037 929445198 418292562 427140491 541966425 427227233 507173798 15060113 682876894 576832970 845820397 792492199 68615189 731761627 450163785 931453098 114106811 789957786 703388594 621979242 943658913 478487619 867755637 600317741 896322862 86822339 199653041 498681386 570165467 889780543 40162521 577406223 700182198 728347275 42355765 495736444 868646112 977999284 56376160 237582470 905217551 389131639 269172939 233220405 638921229 815463367 913275193 531534085 836976694 622596171 286542401 51249513 242957822 880948445 160350928 838283587 631616361 434182156 424192932 131996526 884299153 54518171 950183889 854779189 628016420 466856704 326117696 432469720 593662692 807790566 493198635 773256718 843341349 705544363 743642787 971185790 316212050 144268514 508089098 946468933 478191208 583437267 35651225 101626995 426718584 498182390 987284699 810612109 652668714 388116604 784338736 428854797 922006837 807824326 644141899 278364893 952503016 690686955 452241333 834702304 201696164 535530551 129178184 900396138 747941728 209320102 600377524 459218370 7207204 327872109 889740029 222539175 591291790 71418482 153053691 116104392 474966352 828156367 39438808 873210699 949549999 18968659 839310998 77264711 643848966 96803584 648609415 890850121 566572353 37420686 250754259 78662355 541851235 80285671 608849397 705102552 936013056 371766953 93464126 614887490 720207555 788161447 526576209 372250221 288204522 904574824 528100261 333960105 577738437 291408551 434671367 755775419 912097338 859646673 323514645 149038684 938449988 371179658 673214147 497819065 295884655 478574632 865332186 497110769 434546270 616365622 989314932 815318682 995682886 974288371 947281538 430627133 862908272 91935185 452578374 529679317 275433402 413113846 823293145 713958484 530605847 818131646 711661990 211624479 512018443 227456311 206251501 805568653 785497135 11664803 379492673 780171627 467852467 490249210 931808266 134004603 285314775 858660965 971952644 242447088 425829489 530384324 419978942 906829299 601701994 546338345 814302237 756010274 517845825 306813275 409795798 155565067 146764166 14646612 626699511 949561270 227066464 363937987 675498590 482957080 597102088 280480139 18964288 259192225 175770700 45415234 12754084 706143151 711276301 857462195 848193254 454671640 715271873 676639068 545316916 652312485 374625009 445103089 672118036 350649745 409545916
